// Copyright 2018 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#pragma once

#include <cstddef>
#include <new>
#include <utility>

#include <lockdep/common.h>
#include <lockdep/guard.h>
#include <lockdep/lock_class.h>

namespace lockdep {

// Guards simultaneous acquisitions of multiple locks of the same type.
template <size_t Size, typename LockType, typename Option = void>
class GuardMultiple {
  // Prevent passing nestable locks to GuardMultiple to avoid inconsistency
  // due to mixing external ordering and address ordering.
  static_assert((LockTraits<LockType>::Flags & LockFlagsNestable) == 0,
                "Nestable locks cannot be used with GuardMultiple!");

 public:
  GuardMultiple(GuardMultiple&&) = delete;
  GuardMultiple& operator=(GuardMultiple&&) = delete;

  GuardMultiple(const GuardMultiple&) = delete;
  GuardMultiple& operator=(const GuardMultiple&) = delete;

  // Locks the given set of locks, each belonging to the same lock class,
  // automatically ordering the arguments by address to preserve the
  // intra-class ordering invariant.
  template <typename Class, size_t Index, template <typename, typename, size_t> class... Locks>
  GuardMultiple(Locks<Class, LockType, Index>*... locks)
      : GuardMultiple{std::make_index_sequence<sizeof...(locks)>{}, locks...} {}

  ~GuardMultiple() {
    // Destroy union storage. Array elements are destroyed in reverse order.
    guard_storage_.~Storage();
  }

  // Releases all of the locks guarded by this instance.
  void Release() {
    for (size_t i = 0; i < Size; i++)
      guard_storage_.guards[i].Release();
  }

  // Returns true if all of the guards are holding acquired locks. In general
  // all of the guards should be in the same state.
  explicit operator bool() const {
    for (size_t i = 0; i < Size; i++) {
      if (!guard_storage_.guards[i])
        return false;
    }
    return true;
  }

 private:
  // Quickly sorts an array of pointers in-place using insertion sort. When
  // Size is 2 this has been observed to instantiate as an inline swap.
  template <typename T>
  static void InsertionSortPointers(T* (&elements)[Size]) {
    size_t i = 1;
    while (i < Size) {
      T* x = elements[i];
      ssize_t j = i - 1;
      while (j >= 0 && elements[j] > x) {
        elements[j + 1] = elements[j];
        j--;
      }
      elements[j + 1] = x;
      i++;
    }
  }

  // Builds an array of Lock<LockType> pointers, sorts the array by ascending
  // address, and then aggregate initializes the union storage. Array elements
  // are constructed in order.
  template <size_t... Is, template <typename> class... Locks>
  GuardMultiple(std::index_sequence<Is...>, Locks<LockType>*... locks) {
    Lock<LockType>* lock_pointers[] = {locks...};
    InsertionSortPointers(lock_pointers);
    new (&guard_storage_) Storage{
        {{OrderedLock, lock_pointers[Is], reinterpret_cast<uintptr_t>(lock_pointers[Is])}...}};
  }

  // Storage type to permit late initialization of the underlying Guard
  // instances. Since Guard objects are not default constructible, using union
  // semantics allows the GuardMultiple constructor to delay initializing the
  // Guard array until after it has sorted the incoming lock pointers. This
  // type also leverages aggregate initialization since we can't use
  // std::array. Unfortunately, GCC only supports direct initialization of
  // C-style arrays through aggregate initialization so that is the only
  // option.
  struct Storage {
    Guard<LockType, Option> guards[Size];
  };

  union {
    Storage guard_storage_;
  };
};

}  // namespace lockdep
